// 两遍扫描；时间复杂度O(n)；空间复杂度O(1)

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size(); 
        for (int i = n - 1; i > 0; i--) {
            if (nums[i - 1] < nums[i]) {
                i = i - 1;
                for (int j = n - 1; j > i; j--) {
                    if (nums[j] > nums[i]) {
                        swap(nums[i], nums[j]);
                        reverse(nums.begin() + i + 1, nums.end());
                        return;
                    }
                }
            }
        }
        reverse(nums.begin(), nums.end());
    }
};